//
// Created by Snow on 2023/5/21.
//
#include"seqlist.cpp"
void sift(RecType R[],int low,int high)
{
    int i=low,j=2*i;//R[j]是R[i]的左孩子
    RecType temp=R[i];
    while(j<=high)
    {
        if(j<high&&R[j].key<R[j+1].key)//若右孩子较大，把j指向右孩子
            j++;
        if(temp.key<R[j].key)//若根节点小于最大孩子的关键字
        {
            R[i]=R[j];//将R[j]调整到双亲结点位置上
            i=j;//修改i和j的值，以便继续向下筛选
            j=2*i;
        }
        else
            break;//若根结点大于或等于最大孩子的关键字，筛选结束
    }
    R[i]=temp;//被筛选结点放到最终位置上
}
void HeapSort(RecType R[],int n)
{
    int i;
    for(i=n/2;i>=1;i--)//循环建立初始堆,调用sift算法└n/2┘次
        sift(R,i,n);
    for(i=n;i>=2;i--)//进行n-1趟完成堆排序，每一趟堆中的元素个数减一
    {
        swap(R[1],R[i]);//将最后一个元素与根R[1]交换
        sift(R,1,i-1);//对R[1..i-1]进行筛选,得到i-1个节点的堆
    }
}
//int main()
//{
//    int n=10;
//    RecType R[MAXL];
//    KeyType a[]={15,18,29,12,35,32,27,23,10,20};
//    CreateList1(R,a,n);
//    DispList1(R,n);
//    HeapSort(R,n);
//    DispList1(R,n);
//    return 1;
//}

int main()
{
	int n=11;
	RecType R[MAXL];
	KeyType a[]={0,9,8,7,6,5,4,3,2,1,0};
	CreateList1(R,a,n);
	DispList1(R,n);
	HeapSort(R,n);
	DispList1(R,n);
	return 1;
}